package com.mamingchao.foundation.QuestionPool;

import java.util.Arrays;

/**
 * 已知一个搜索二叉树的后续遍历数组 postArr，请根据postArr，重建出整颗数，返回新建数的头节点
 * 要求实现题目和题目的对数器
 *
 * 搜索二叉树，BST，左节点都比右节点小，没有重复值
 *
 * 后序遍历的顺序，是先左数，再右数，再头部，所以数组最后一个值，就是整个数的头部
 * Created by mamingchao on 2020/11/24.
 */
public class BSTpostArr {

    //先定义一个树
    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    private static Node createBSTbyPostArr(int[] arr){
        //整个数组的最后一个值，肯定是树的根节点
        //然后在剩下的 数组里面找出这个root的 所有左边子孙节点和右边子孙节点
        //再用同样的逻辑，分别从左边子树和右边子树找出他们的root
        //每次都搞定root，这个事情就搞定了
        if (arr.length == 0)
            return null;

        int rootValue = arr[arr.length-1];
        Node root = new Node(rootValue);

        if (arr.length == 1) {
            return root;
        }

        //拿出去整个树 root 的value后，数组左侧是比root值小的，右侧是比root值打的值
        //效率最高的就是二分法，找到左右两个分界点，然后再分别找到左测的树的root和右侧树的root

        int L = 0;
        int R = arr.length-2;
        int mid = 0;

        while(L < R) {
            mid = L + ((R-L) >>1);
            //右侧可以不用关心了，在左侧寻找
            if (arr[mid] > rootValue) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        mid = L;

        //如果中间点落在左侧偏小的位置上，比如例子中的2 上
        if (arr[mid] < rootValue) {
            root.left = createBSTbyPostArr(Arrays.copyOf(arr,mid + 1));
            root.right = createBSTbyPostArr(Arrays.copyOfRange(arr,mid + 1,arr.length-mid-1));
        } else if(arr[mid] > rootValue) { //如果中间点落在右侧偏大的位置上，比如例子中的10 上
            root.left = createBSTbyPostArr(Arrays.copyOf(arr,mid));
            root.right = createBSTbyPostArr(Arrays.copyOfRange(arr,mid,arr.length-mid));
        } else if(R == arr.length-2){ // 整个树只有左节点
            root.left = createBSTbyPostArr(Arrays.copyOf(arr,arr.length-2));
        } else if (L ==0 ){ // 整个树只有右节点
            root.right = createBSTbyPostArr(Arrays.copyOf(arr,arr.length-2));
        }

        return  root;

    }

    //console 打印二叉树（图形化形式） 没搞定
    private static void printTree(Node root,int arrLength){
        printProcessor(root,0, arrLength);
    }


    private static void printProcessor(Node node,int width,int height){


        if (node.right != null) {
            printProcessor(node.right,++width,--height);
            for (int i = 0; i < height; i++) {
                System.out.println();
            }
            for (int i = 0; i < width; i++) {
                System.out.print("  ");
            }
        }


        System.out.println();
        for (int i = 0; i < width-1; i++) {
            System.out.print("  ");
        }
        System.out.print(node.value);


        if (node.left != null) {
            printProcessor(node.left,++width,++height);
            for (int i = 0; i < height; i++) {
                System.out.println();
            }
            for (int i = 0; i < width; i++) {
                System.out.print("  ");
            }
        }
    }

    //TODO 对数器

    public static void main(String[] args) {
//        int[] arr = new int[]{1};
//        int[] arr = new int[]{1,5,4,3,2,10,8,7,9,11,15,14,18,17,6};
//        int[] arr = new int[]{1,5,4,3,2,10,14,6};
        int[] arr = new int[]{1,4,6,5,2};
        Node node = createBSTbyPostArr(arr);

        printTree(node,arr.length);

    }

}
